//实现自己的Linkedlist
public class MyLinkedlist implements singLinklist{


    static class LinkNode{
        private int val;
        private LinkNode next;

        public LinkNode(int val) {
            this.val = val;
        }
    }
    public LinkNode head;//表示当前链表的头部
    private int Listsize;//表示链表元素个数

    //创建一个链表
  /*  public void creatlink(){
        LinkNode node1=new LinkNode(10);
        LinkNode node2=new LinkNode(20);
        LinkNode node3=new LinkNode(30);
        LinkNode node4=new LinkNode(40);
        LinkNode node5=new LinkNode(50);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        head=node1;
    }*/
    @Override
    public void addFirst(int data) {
        LinkNode node=new LinkNode(data);
        if(head==null){
            head=node;
            Listsize++;
            return;
        }
        else {
            node.next=head;
            head=node;
            Listsize++;
        }
    }

    @Override
    public void addLast(int data) {
        LinkNode node=new LinkNode(data);
        if(head==null){//head==null代表没有一个元素
            head=node;
            Listsize++;
            return;
        }
        LinkNode cut=head;
        while (cut.next!=null){
            cut=cut.next;
        }
          cut.next=node;
        Listsize++;

    }

    @Override
    public void addIndex(int index, int data) {
        chekindex(index);
        LinkNode node=new LinkNode(data);
        LinkNode cut=head;
        if(index==0){
            addFirst(data);
        }
        else if (index==Listsize){
            addLast(data);
        }
        else {
         FindIndex(index);
         node.next=cut.next;
         cut.next=node;
        }
        Listsize++;
    }
    private void chekindex(int index){
        if(index<0||index>size()){
            throw new RuntimeException("index超出范围");
        }
    }
    private LinkNode FindIndex(int index){
        LinkNode cut=head;
        int count=0;
        while (count!=index-1){
            cut=cut.next;
            count++;
        }
        return cut;
    }

    @Override
    public boolean contains(int key) {
        LinkNode cut=head;
        while (cut!=null){
            if(cut.val==key){
                return true;
            }
            cut=cut.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null){
            return;
        }
        if (head.val==key) {
            head=head.next;
            Listsize--;
            return;
        }
        LinkNode cut= Findkey(key);
        LinkNode temp=cut.next;
        if(cut==null){
            System.out.println("没有你要找的数据");
        }
        else {
            cut.next=temp.next;
            Listsize--;
        }
    }
    private LinkNode Findkey(int key){
        LinkNode cut=head;
        while (cut.next!=null){
            if(cut.next.val==key){
                return cut;
            }
            cut=cut.next;
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {//还不理解
        if(head==null){
            return;
        }
       /* if (head.val==key){//防止第二个元素.val还是等于key可以使用while
                           //但是如果全部元素.val都是key会导致最后head.next越界
            head=head.next;
            Listsize--;
        }*/
        LinkNode cur=head.next;
        LinkNode per=head;
        while (cur!=null){
            if(cur.val==key){
                per.next=cur.next;
                cur=cur.next;
                Listsize--;
            }
            else {
                per=cur;
                cur=cur.next;
            }
        }
//所以等除第一个元素都遍历后再去判断第一个元素
        if (head.val==key){
            head=head.next;
            Listsize--;
        }


    }

    @Override
    public int size() {
       /* LinkNode cut=head;
        int temp = 0;
        while (cut!=null) {
            cut = cut.next;
            temp++;
        }*/
        return Listsize;
    }

    @Override
    public void clear() {
        head=null;
        Listsize=0;
    }

    @Override
    public void display() {
        LinkNode cut=head;
        while (cut!=null){
            System.out.println(cut.val);
            cut=cut.next;
        }
        System.out.println();
    }

    @Override
    public void display(LinkNode nehead) {
        //不能直接使用head走循环不然head就直接在null不能再表示头元素了
        LinkNode cut=nehead;
        while (cut!=null){
            System.out.println(cut.val);
            cut=cut.next;
        }
        System.out.println();
    }
    public static MyLinkedlist.LinkNode mergeTwoLists(MyLinkedlist.LinkNode list1, MyLinkedlist.LinkNode list2) {
        MyLinkedlist.LinkNode Hew=new LinkNode(-1);
        MyLinkedlist.LinkNode temp=Hew;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                temp.next=list1;//使用temp.next去连链表
                list1=list1.next;
            }
            else{
                temp.next=list2;
                list2=list2.next;
            }
            temp=temp.next;
        }

        if(list1!=null){
            temp.next=list1;
        }
        if(list2!=null){
            temp.next=list2;
        }
        return Hew.next;
    }
    public static void main1(String[] args) {
        MyLinkedlist myLinkedlist=new MyLinkedlist();
        myLinkedlist.addFirst(60);
        myLinkedlist.addFirst(50);
        myLinkedlist.addFirst(40);
        myLinkedlist.addFirst(20);
        myLinkedlist.addFirst(20);
        myLinkedlist.addFirst(10);
        myLinkedlist.addIndex(1,88);
        myLinkedlist.remove(10);
        myLinkedlist.removeAllKey(20);

        myLinkedlist.display();
        myLinkedlist.clear();
        myLinkedlist.display();
        System.out.println(myLinkedlist.size());
        System.out.println(myLinkedlist.contains(50));
    }

    public static void main(String[] args) {
        MyLinkedlist myLinkedlist=new MyLinkedlist();
        myLinkedlist.addFirst(60);
        myLinkedlist.addFirst(50);
        myLinkedlist.addFirst(40);
        myLinkedlist.addFirst(20);
        myLinkedlist.addFirst(20);
        myLinkedlist.addFirst(10);
        MyLinkedlist myLinkedlist1=new MyLinkedlist();
        myLinkedlist.addFirst(66);
        myLinkedlist.addFirst(55);
        myLinkedlist.addFirst(44);
        MyLinkedlist.LinkNode ret=mergeTwoLists(myLinkedlist1.head,myLinkedlist.head);
        myLinkedlist.display(ret);


    }
}
